package com.dataStructures.sort;

import java.util.Arrays;

/**
 * 快速排序 时间复杂度 O(nlogn)
 */
public class QuickSort {
	public static void main(String[] args) {
		int[] arr = {14, 2, 8, 3, 9, 1, -5, 67, 0};
		System.out.println("排序前：" + Arrays.toString(arr));
		quickSort(arr, 0, arr.length - 1);
		System.out.println("排序后：" + Arrays.toString(arr));

		// 批量测试
		int[] arrBatch = new int[100000];
		for (int i = 0; i < 100000; i++) {
			arrBatch[i] = (int) (Math.random() * 100000);
		}
		long begin = System.currentTimeMillis();
		quickSort(arrBatch, 0, arrBatch.length - 1);
		System.out.println("coast time:" + (System.currentTimeMillis() - begin));
	}

	/**
	 * 快速排序
	 */
	public static void quickSort(int[] arr, int left, int right) {
		// 左下标
		int l = left;
		// 右下标
		int r = right;
		// 中轴值
		int pivot = arr[(left + right) / 2];

		int temp;

		while (l < r) {
			// 遍历让中轴左边都小于中轴值
			while (arr[l] < pivot) {
				l++;
			}
			// 遍历让中轴右边都大于中轴值
			while (arr[r] > pivot) {
				r--;
			}

			// 退出循环
			if (l >= r) {
				break;
			}

			// 左右交换
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;

			// 左或右 有一边等于中轴值，则只遍历另一边
			if (arr[l] == pivot) {
				r--;
			}
			if (arr[r] == pivot) {
				l++;
			}
		}

		// 确定下一次二分的边界
		if (l == r) {
			l--;
			r++;
		}

		if (left < l) {
			quickSort(arr, left, l);
		}
		if (right > r) {
			quickSort(arr, r, right);
		}
	}
}
